package leetcode.code0906;

public class Solution extends Solution906 {

	@Override
	public int superpalindromesInRange(String left, String right) {
		long LL = Long.valueOf(left);
		long RR = Long.valueOf(right);
		long nn = 0;
		int ans = 0;
		long start = 1;
		while (start < 10) {
			nn = start * start;
			if (nn >= LL && nn <= RR && this.isPalindromes(nn)) {
				ans++;
			}
			start++;
		}
		int L = Math.max(this.sqrt(LL), 10);
		int R = this.sqrt(RR) + 1;
		int len = this.len(L) >> 1;
		int tmp = len >> 1;
		while (tmp > 0) {
			L /= 10;
			R /= 10;
			tmp--;
		}
		if ((len & 1) == 1) {
			L /= 10;
			R /= 10;
		}
//		L = Math.max(L, 1);
//		for (int i = L; i <= R; i++) {
		while (true && nn <= RR) {
			long[] nums = this.create(L);
			for (long num : nums) {
				nn = num * num;
				if (nn >= LL && nn <= RR && this.isPalindromes(nn)) {
					ans++;
				}
			}
			L++;
		}
		return ans;
	}

	public boolean isPalindromes(long num) {
		if (num < 10) {
			if (num == 0)
				return false;
			return true;
		}
		long mirror = 0;
		long mod = 0;
		long tmp = num;
		while (tmp > 0) {
			mod = tmp % 10;
			mirror = mirror * 10 + mod;
			tmp /= 10;
		}
		return num == mirror;
	}

	public long[] create(int start) {
		long[] ans = new long[11];
		int mul = 1;
		int tmp = start;
		int mirror = 0;
		int mod = 0;
		while (tmp > 0) {
			mod = tmp % 10;
			mirror = mirror * 10 + mod;
			tmp /= 10;
			mul *= 10;
		}
		ans[10] = start * mul + mirror;
		tmp = start * mul * 10 + mirror;
		for (int i = 0; i < 10; i++) {
			ans[i] = tmp + i * mul;
		}
		return ans;
	}

	public int len(int num) {
		int ans = 0;
		while (num > 0) {
			num /= 10;
			ans++;
		}
		return ans;
	}

	public int sqrt(long num) {
		return (int) Math.sqrt(num);
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug3();
//		so.debug2();
//		so.debug1();
//		System.out.println(so.sqrt(678));
//		System.out.println(27 * 27);
//		System.out.println(7 >> 1);
//		long ans = so.createPalindromesEven(156);
//		System.out.println(ans + " " + ans * ans);
//		long ans1 = so.createPalindromesOdd(156, 0);
//		System.out.println(ans1 + " " + ans1 * ans1);
//		System.out.println(so.isPalindromes(1230321));
//		long[] ans = so.create(46);
//		for (long l : ans) {
//			System.out.println(l);
//		}
	}

}
